package leetcode.binarytree;

/**
 * 二叉树中的最大路径和 困难
 */
public class Solution124二叉树中的最大路径和 {
//    二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。
//    该路径 至少包含一个 节点，且不一定经过根节点。
//
//    路径和 是路径中各节点值的总和。

//    输入：root = [-10,9,20,null,null,15,7]
//    输出：42
//    解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

//        -10
//    9          20
//          15        7

    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(10);

        TreeNode leftTreeNode = new TreeNode(9);
        treeNode.left = leftTreeNode;

        TreeNode rightTreeNode = new TreeNode(20);
        treeNode.right = rightTreeNode;

        TreeNode leftTreeNode20 = new TreeNode(15);
        rightTreeNode.left = leftTreeNode20;
        TreeNode rightTreeNode20 = new TreeNode(7);
        rightTreeNode.right = rightTreeNode20;

        Solution124二叉树中的最大路径和 solution124 = new Solution124二叉树中的最大路径和();
        solution124.maxPathSum(treeNode);
    }
}
